package basic.study.algorithms.struct.BST.Balanced;

/**
 * @author Kevin
 * @date 2020/3/6 20:38
 */
public class AVLTree {
    Node root=null;                     //根节点
    final int LH =+1;                        /*  左高 */
    final int EH= 0;                            /*  等高 */
    final int RH=-1;                           /*  右高 */
    final int LC=0;                         //在左子树插入
    final int RC=1;							//在右子树插入
    final boolean FALSE=false;
    final boolean TRUE=true;

    /* 对以T为根的二叉排序树作右旋处理 */
    /* 处理之后T的父节点指向T的左节点 */
    //右旋-顺时针旋转(如LL型就得对根结点做该旋转)
    //逻辑：先把左-左情况的左-右节点挂到根节点右，然后旋转
    private void R_Rotate(Node T)
    {
        Node L,P;
        P=T.parent;
        L=T.lchild;                      /*  L指向node的左子树根结点 */
        T.lchild=L.rchild;               /*  L的右子树挂接为node的左子树 */

        if(L.rchild!=null)
            L.rchild.parent=T;
        L.rchild=T;
        L.parent=P;
        T.parent=L;

        if(P==null)
            root=L;
        else if(P.rchild==T)
            P.rchild=L;
        else
            P.lchild=L;

    }

    /* 对以T为根的二叉排序树作左旋处理， */
    /* 处理之后T的父节点指向T的右节点 */
    //左旋-逆时针旋转(如RR型就得对根结点做该旋转)
    //逻辑：先把右-右情况的右-左节点挂到根节点右，然后旋转
    private void L_Rotate(Node T)
    {
        Node R,P;
        P=T.parent;
        R = T.rchild;                    /* R指向T的右子树根结点 */
        T.rchild = R.lchild;         /* R的左子树挂接为T的右子树 */

        if(R.lchild!=null)
            R.lchild.parent=T;
        R.lchild = T;
        R.parent=P;
        T.parent=R;

        if(P==null)
            root=R;
        else if(P.rchild==T)
            P.rchild=R;
        else
            P.lchild=R;

    }


    private class Node{
        int value;
        int bf;
        Node lchild;
        Node rchild;
        Node parent;
        public Node(int value,int bf,Node lchild,Node rchild,Node parent){
            this.value=value;
            this.bf=bf;
            this.lchild=lchild;
            this.rchild=rchild;
            this.parent=parent;
        }
    }
}
